home *** CD-ROM | disk | FTP | other *** search
/ Ian & Stuart's Australian Mac: Not for Sale / Another.not.for.sale (Australia).iso / hold me in your arms / PGP 2.6 / rsaref Toolkit / source / rsa.c < prev    next >
C/C++ Source or Header  |  1992-02-29  |  10KB  |  325 lines
  1. /* RSA.C - RSA routines for RSAREF
  2.  */
  3.  
  4. /* Copyright (C) 1991-2 RSA Laboratories, a division of RSA Data
  5.    Security, Inc. All rights reserved.
  6.  */
  7.  
  8. #include "global.h"
  9. #include "rsaref.h"
  10. #include "r_random.h"
  11. #include "rsa.h"
  12. #include "nn.h"
  13.  
  14. static int RSAPublicBlock PROTO_LIST 
  15.   ((unsigned char *, unsigned int *, unsigned char *, unsigned int,
  16.     R_RSA_PUBLIC_KEY *));
  17. static int RSAPrivateBlock PROTO_LIST 
  18.   ((unsigned char *, unsigned int *, unsigned char *, unsigned int,
  19.     R_RSA_PRIVATE_KEY *));
  20.  
  21. /* RSA public-key encryption, according to PKCS #1.
  22.  */
  23. int RSAPublicEncrypt
  24.   (output, outputLen, input, inputLen, publicKey, randomStruct)
  25. unsigned char *output;                                      /* output block */
  26. unsigned int *outputLen;                          /* length of output block */
  27. unsigned char *input;                                        /* input block */
  28. unsigned int inputLen;                             /* length of input block */
  29. R_RSA_PUBLIC_KEY *publicKey;                              /* RSA public key */
  30. R_RANDOM_STRUCT *randomStruct;                          /* random structure */
  31. {
  32.   int status;
  33.   unsigned char byte, pkcsBlock[MAX_RSA_MODULUS_LEN];
  34.   unsigned int i, modulusLen;
  35.   
  36.   modulusLen = (publicKey->bits + 7) / 8;
  37.   if (inputLen + 11 > modulusLen)
  38.     return (RE_LEN);
  39.   
  40.   pkcsBlock[0] = 0;
  41.   /* block type 2 */
  42.   pkcsBlock[1] = 2;
  43.  
  44.   for (i = 2; i < modulusLen - inputLen - 1; i++) {
  45.     /* Find nonzero random byte.
  46.      */
  47.     do {
  48.       R_GenerateBytes (&byte, 1, randomStruct);
  49.     } while (byte == 0);
  50.     pkcsBlock[i] = byte;
  51.   }
  52.   /* separator */
  53.   pkcsBlock[i++] = 0;
  54.   
  55.   R_memcpy ((POINTER)&pkcsBlock[i], (POINTER)input, inputLen);
  56.   
  57.   status = RSAPublicBlock
  58.     (output, outputLen, pkcsBlock, modulusLen, publicKey);
  59.   
  60.   /* Zeroize sensitive information.
  61.    */
  62.   byte = 0;
  63.   R_memset ((POINTER)pkcsBlock, 0, sizeof (pkcsBlock));
  64.   
  65.   return (status);
  66. }
  67.  
  68. /* RSA public-key decryption, according to PKCS #1.
  69.  */
  70. int RSAPublicDecrypt (output, outputLen, input, inputLen, publicKey)
  71. unsigned char *output;                                      /* output block */
  72. unsigned int *outputLen;                          /* length of output block */
  73. unsigned char *input;                                        /* input block */
  74. unsigned int inputLen;                             /* length of input block */
  75. R_RSA_PUBLIC_KEY *publicKey;                              /* RSA public key */
  76. {
  77.   int status;
  78.   unsigned char pkcsBlock[MAX_RSA_MODULUS_LEN];
  79.   unsigned int i, modulusLen, pkcsBlockLen;
  80.   
  81.   modulusLen = (publicKey->bits + 7) / 8;
  82.   if (inputLen > modulusLen)
  83.     return (RE_LEN);
  84.   
  85.   if (status = RSAPublicBlock
  86.       (pkcsBlock, &pkcsBlockLen, input, inputLen, publicKey))
  87.     return (status);
  88.   
  89.   if (pkcsBlockLen != modulusLen)
  90.     return (RE_LEN);
  91.   
  92.   /* Require block type 1.
  93.    */
  94.   if ((pkcsBlock[0] != 0) || (pkcsBlock[1] != 1))
  95.    return (RE_DATA);
  96.  
  97.   for (i = 2; i < modulusLen-1; i++)
  98.     if (pkcsBlock[i] != 0xff)
  99.       break;
  100.     
  101.   /* separator */
  102.   if (pkcsBlock[i++] != 0)
  103.     return (RE_DATA);
  104.   
  105.   *outputLen = modulusLen - i;
  106.   
  107.   if (*outputLen + 11 > modulusLen)
  108.     return (RE_DATA);
  109.  
  110.   R_memcpy ((POINTER)output, (POINTER)&pkcsBlock[i], *outputLen);
  111.   
  112.   /* Zeroize potentially sensitive information.
  113.    */
  114.   R_memset ((POINTER)pkcsBlock, 0, sizeof (pkcsBlock));
  115.   
  116.   return (0);
  117. }
  118.  
  119. /* RSA private-key encryption, according to PKCS #1.
  120.  */
  121. int RSAPrivateEncrypt (output, outputLen, input, inputLen, privateKey)
  122. unsigned char *output;                                      /* output block */
  123. unsigned int *outputLen;                          /* length of output block */
  124. unsigned char *input;                                        /* input block */
  125. unsigned int inputLen;                             /* length of input block */
  126. R_RSA_PRIVATE_KEY *privateKey;                           /* RSA private key */
  127. {
  128.   int status;
  129.   unsigned char pkcsBlock[MAX_RSA_MODULUS_LEN];
  130.   unsigned int i, modulusLen;
  131.   
  132.   modulusLen = (privateKey->bits + 7) / 8;
  133.   if (inputLen + 11 > modulusLen)
  134.     return (RE_LEN);
  135.   
  136.   pkcsBlock[0] = 0;
  137.   /* block type 1 */
  138.   pkcsBlock[1] = 1;
  139.  
  140.   for (i = 2; i < modulusLen - inputLen - 1; i++)
  141.     pkcsBlock[i] = 0xff;
  142.  
  143.   /* separator */
  144.   pkcsBlock[i++] = 0;
  145.   
  146.   R_memcpy ((POINTER)&pkcsBlock[i], (POINTER)input, inputLen);
  147.   
  148.   status = RSAPrivateBlock
  149.     (output, outputLen, pkcsBlock, modulusLen, privateKey);
  150.  
  151.   /* Zeroize potentially sensitive information.
  152.    */
  153.   R_memset ((POINTER)pkcsBlock, 0, sizeof (pkcsBlock));
  154.  
  155.   return (status);
  156. }
  157.  
  158. /* RSA private-key decryption, according to PKCS #1.
  159.  */
  160. int RSAPrivateDecrypt (output, outputLen, input, inputLen, privateKey)
  161. unsigned char *output;                                      /* output block */
  162. unsigned int *outputLen;                          /* length of output block */
  163. unsigned char *input;                                        /* input block */
  164. unsigned int inputLen;                             /* length of input block */
  165. R_RSA_PRIVATE_KEY *privateKey;                           /* RSA private key */
  166. {
  167.   int status;
  168.   unsigned char pkcsBlock[MAX_RSA_MODULUS_LEN];
  169.   unsigned int i, modulusLen, pkcsBlockLen;
  170.   
  171.   modulusLen = (privateKey->bits + 7) / 8;
  172.   if (inputLen > modulusLen)
  173.     return (RE_LEN);
  174.   
  175.   if (status = RSAPrivateBlock
  176.       (pkcsBlock, &pkcsBlockLen, input, inputLen, privateKey))
  177.     return (status);
  178.   
  179.   if (pkcsBlockLen != modulusLen)
  180.     return (RE_LEN);
  181.   
  182.   /* Require block type 2.
  183.    */
  184.   if ((pkcsBlock[0] != 0) || (pkcsBlock[1] != 2))
  185.    return (RE_DATA);
  186.  
  187.   for (i = 2; i < modulusLen-1; i++)
  188.     /* separator */
  189.     if (pkcsBlock[i] == 0)
  190.       break;
  191.     
  192.   i++;
  193.   if (i >= modulusLen)
  194.     return (RE_DATA);
  195.     
  196.   *outputLen = modulusLen - i;
  197.   
  198.   if (*outputLen + 11 > modulusLen)
  199.     return (RE_DATA);
  200.  
  201.   R_memcpy ((POINTER)output, (POINTER)&pkcsBlock[i], *outputLen);
  202.   
  203.   /* Zeroize sensitive information.
  204.    */
  205.   R_memset ((POINTER)pkcsBlock, 0, sizeof (pkcsBlock));
  206.   
  207.   return (0);
  208. }
  209.  
  210. /* Raw RSA public-key operation. Output has same length as modulus.
  211.  
  212.    Assumes inputLen < length of modulus.
  213.    Requires input < modulus.
  214.  */
  215. static int RSAPublicBlock (output, outputLen, input, inputLen, publicKey)
  216. unsigned char *output;                                      /* output block */
  217. unsigned int *outputLen;                          /* length of output block */
  218. unsigned char *input;                                        /* input block */
  219. unsigned int inputLen;                             /* length of input block */
  220. R_RSA_PUBLIC_KEY *publicKey;                              /* RSA public key */
  221. {
  222.   NN_DIGIT c[MAX_NN_DIGITS], e[MAX_NN_DIGITS], m[MAX_NN_DIGITS],
  223.     n[MAX_NN_DIGITS];
  224.   unsigned int eDigits, nDigits;
  225.  
  226.   NN_Decode (m, MAX_NN_DIGITS, input, inputLen);
  227.   NN_Decode (n, MAX_NN_DIGITS, publicKey->modulus, MAX_RSA_MODULUS_LEN);
  228.   NN_Decode (e, MAX_NN_DIGITS, publicKey->exponent, MAX_RSA_MODULUS_LEN);
  229.   nDigits = NN_Digits (n, MAX_NN_DIGITS);
  230.   eDigits = NN_Digits (e, MAX_NN_DIGITS);
  231.   
  232.   if (NN_Cmp (m, n, nDigits) >= 0)
  233.     return (RE_DATA);
  234.   
  235.   /* Compute c = m^e mod n.
  236.    */
  237.   NN_ModExp (c, m, e, eDigits, n, nDigits);
  238.  
  239.   *outputLen = (publicKey->bits + 7) / 8;
  240.   NN_Encode (output, *outputLen, c, nDigits);
  241.   
  242.   /* Zeroize sensitive information.
  243.    */
  244.   R_memset ((POINTER)c, 0, sizeof (c));
  245.   R_memset ((POINTER)m, 0, sizeof (m));
  246.  
  247.   return (0);
  248. }
  249.  
  250. /* Raw RSA private-key operation. Output has same length as modulus.
  251.  
  252.    Assumes inputLen < length of modulus.
  253.    Requires input < modulus.
  254.  */
  255. static int RSAPrivateBlock (output, outputLen, input, inputLen, privateKey)
  256. unsigned char *output;                                      /* output block */
  257. unsigned int *outputLen;                          /* length of output block */
  258. unsigned char *input;                                        /* input block */
  259. unsigned int inputLen;                             /* length of input block */
  260. R_RSA_PRIVATE_KEY *privateKey;                           /* RSA private key */
  261. {
  262.   NN_DIGIT c[MAX_NN_DIGITS], cP[MAX_NN_DIGITS], cQ[MAX_NN_DIGITS],
  263.     dP[MAX_NN_DIGITS], dQ[MAX_NN_DIGITS], mP[MAX_NN_DIGITS],
  264.     mQ[MAX_NN_DIGITS], n[MAX_NN_DIGITS], p[MAX_NN_DIGITS], q[MAX_NN_DIGITS],
  265.     qInv[MAX_NN_DIGITS], t[MAX_NN_DIGITS];
  266.   unsigned int cDigits, nDigits, pDigits;
  267.   
  268.   NN_Decode (c, MAX_NN_DIGITS, input, inputLen);
  269.   NN_Decode (n, MAX_NN_DIGITS, privateKey->modulus, MAX_RSA_MODULUS_LEN);
  270.   NN_Decode (p, MAX_NN_DIGITS, privateKey->prime[0], MAX_RSA_PRIME_LEN);
  271.   NN_Decode (q, MAX_NN_DIGITS, privateKey->prime[1], MAX_RSA_PRIME_LEN);
  272.   NN_Decode 
  273.     (dP, MAX_NN_DIGITS, privateKey->primeExponent[0], MAX_RSA_PRIME_LEN);
  274.   NN_Decode 
  275.     (dQ, MAX_NN_DIGITS, privateKey->primeExponent[1], MAX_RSA_PRIME_LEN);
  276.   NN_Decode (qInv, MAX_NN_DIGITS, privateKey->coefficient, MAX_RSA_PRIME_LEN);
  277.   cDigits = NN_Digits (c, MAX_NN_DIGITS);
  278.   nDigits = NN_Digits (n, MAX_NN_DIGITS);
  279.   pDigits = NN_Digits (p, MAX_NN_DIGITS);
  280.  
  281.   if (NN_Cmp (c, n, nDigits) >= 0)
  282.     return (RE_DATA);
  283.   
  284.   /* Compute mP = cP^dP mod p  and  mQ = cQ^dQ mod q. (Assumes q has
  285.      length at most pDigits, i.e., p > q.)
  286.    */
  287.   NN_Mod (cP, c, cDigits, p, pDigits);
  288.   NN_Mod (cQ, c, cDigits, q, pDigits);
  289.   NN_ModExp (mP, cP, dP, pDigits, p, pDigits);
  290.   NN_AssignZero (mQ, nDigits);
  291.   NN_ModExp (mQ, cQ, dQ, pDigits, q, pDigits);
  292.   
  293.   /* Chinese Remainder Theorem:
  294.        m = ((((mP - mQ) mod p) * qInv) mod p) * q + mQ.
  295.    */
  296.   if (NN_Cmp (mP, mQ, pDigits) >= 0)
  297.     NN_Sub (t, mP, mQ, pDigits);
  298.   else {
  299.     NN_Sub (t, mQ, mP, pDigits);
  300.     NN_Sub (t, p, t, pDigits);
  301.   }
  302.   NN_ModMult (t, t, qInv, p, pDigits);
  303.   NN_Mult (t, t, q, pDigits);
  304.   NN_Add (t, t, mQ, nDigits);
  305.  
  306.   *outputLen = (privateKey->bits + 7) / 8;
  307.   NN_Encode (output, *outputLen, t, nDigits);
  308.  
  309.   /* Zeroize sensitive information.
  310.    */
  311.   R_memset ((POINTER)c, 0, sizeof (c));
  312.   R_memset ((POINTER)cP, 0, sizeof (cP));
  313.   R_memset ((POINTER)cQ, 0, sizeof (cQ));
  314.   R_memset ((POINTER)dP, 0, sizeof (dP));
  315.   R_memset ((POINTER)dQ, 0, sizeof (dQ));
  316.   R_memset ((POINTER)mP, 0, sizeof (mP));
  317.   R_memset ((POINTER)mQ, 0, sizeof (mQ));
  318.   R_memset ((POINTER)p, 0, sizeof (p));
  319.   R_memset ((POINTER)q, 0, sizeof (q));
  320.   R_memset ((POINTER)qInv, 0, sizeof (qInv));
  321.   R_memset ((POINTER)t, 0, sizeof (t));
  322.  
  323.   return (0);
  324. }
  325.